#include<stdio.h>

/*
 * 这是快速排序的示例
 * 
 * 作者：Tmacy
 * 时间：2013-11-27
 *
 */
int partition(int *a,int p,int r);

void quick_sort(int *a,int p,int r);

int main(int argc, const char *argv[])
{
    int a[10] = {10,3,2,5,9,0,1,4,4,6};

    quick_sort(a,0,9);

    for(int i = 0;i < 10;i++){
        printf("a :%d ",a[i]);
    }
    putchar(10);
    
    return 0;
}

int partition(int *a,int p,int r){

    int x = a[r];
    int i = p - 1;          // i 标记了数组元素值小于a[r]的位置
    int temp;
 

    for(int j = p;j < r;j++){
        if(a[j] <= x){
            i++;
            temp = a[i];    //不要用异或交换，会出现自己异或清零情况
            a[i] = a[j];
            a[j] = temp;
        }
    }
    temp        =  a[i + 1];
    a[i + 1]    =  a[r];
    a[r]        =  temp;

   
    return i + 1;
}

void quick_sort(int *a,int p,int r){
    int q = 0;

    if(p < r){
        q = partition(a,p,r);
        quick_sort(a,p,q - 1);
        quick_sort(a,q + 1,r);
    }
}
